bzoj 4817 [Sdoi2017]树点涂色

发表于 | 分类于 ， |

题目链接

bzoj4817: [Sdoi2017]树点涂色

题解

数据结构…..大概很容易看出是道lct 然后弃疗
操作1很想lct里面的access操作
那么对于操作2
设F[i]=i点到lct根路径上的splay数（也就是虚边数）+1
那么对于操作2的(x,y)
ans(x,y)=F[x]+F[y]-(F(lca(x,y)))+1;
对于操作3的(x),就是在x的子树中取max，我们可以用dfs序+线段树维护
考虑操作1对操作3的影响
在access的时候，当一个边由虚变实，此时该边所连的深度大的点的颜色种类-1
反之当一边由实变虚，此时该边所连的深度大的点的颜色种类+1
trick:保存当前节点在树中最左儿子的编号用以修改区间(即left[])
ps:中途电脑爆炸,然后重码QAQ，心态爆炸

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
/*
 *
 * 数据结构+LCT+SEG_TREE
 *  
 */
#include<cstdio>
#include<algorithm>
const int maxn = 100007;
int n,m;
struct node{
    int v,next;
}edge[maxn<<1];
int head[maxn],num;
void Add_Edge(int u,int v) {
    edge[++num].v=v;edge[num].next=head[u];head[u]=num;
}
int idfn[maxn],ldfn[maxn],rdfn[maxn],f[maxn][20],dep[maxn];
int cnt=0,fa[maxn];
void dfs(int u,int F) {
    idfn[ldfn[u]=++cnt]=u,f[u][0]=fa[u]=F;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v!=F) dep[v]=dep[u]+1,dfs(v,u);
    }
    rdfn[u]=cnt;
    return ;
}
int LCA(int x,int y) {
    if(dep[x]<dep[y]) std::swap(x,y);
    for(int i=dep[x]-dep[y],j=0;i;i>>=1,++j)
        if(i&1)x=f[x][j];
    if(x==y) return x;
    for(int i=19;~i;--i) 
        if(f[x][i]!=f[y][i]) 
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
class Segment_Tree {
#define lc x<<1
#define rc x<<1|1
    private :
        
        struct Node {
            int max,tag;
            Node () : tag(0){}
        };
        Node t[maxn<<2];
        
        void update(int x) {
            t[x].max=std::max(t[lc].max,t[rc].max);
        }
        void push_down(int x) {
            if(!t[x].tag)return;
            int k=t[x].tag;
            t[lc].max+=k;
            t[lc].tag+=k;
            t[rc].max+=k;
            t[rc].tag+=k;
            t[x].tag=0;
            return ;
        }
        
    public :
        void build (int x,int l,int r) {
            if(l==r) {
                t[x].max=dep[idfn[l]]+1;return;
            }
            int mid=l+r>>1;
            build(lc,l,mid);
            build(rc,mid+1,r);
            return update(x);
        }
        void modify(int x,int l,int r,int L,int  R,int w) {
            if(L<=l&&R>=r) {
                t[x].tag+=w;t[x].max+=w;
                return ;
            }
            push_down(x);
            int mid=l+r>>1;
            if(mid>=L) modify(lc,l,mid,L,R,w);
            if(mid<R) modify(rc,mid+1,r,L,R,w);
            return update(x);
        }
        
        int query(int x,int l,int r,int L,int  R) {
            if(L<=l&&R>=r) 
                return t[x].max;
            push_down(x);
            int mid=l+r>>1,ans=0;
            if(mid>=L) ans=std::max(ans,query(lc,l,mid,L,R));
            if(mid<R) ans=std::max(ans,query(rc,mid+1,r,L,R));
            return ans;
        }
#undef lc
#undef rc
}SEG_T;
class Link_Cut_tree {
#define lc ch[x][0]
#define rc ch[x][1]
    private : 
        
        int ch[maxn][2],left[maxn];
    void update(int x) {
        left[x]=lc ? left[lc]:x;
    }
    
    bool isroot(int x) {
        return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
    }
    
    void rotate(int x) {
        int y=fa[x],z=fa[y],d=(ch[y][1]==x)^1;
        if(!isroot(y)) ch[z][ch[z][1]==y]=x;fa[x]=z;
        ch[y][d^1]=ch[x][d],fa[ch[x][d]]=y;
        ch[x][d]=y;fa[y]=x;
        update(y),update(x);
    }
    
    void splay(int x) {
        while(!isroot(x)) {
            int y=fa[x],z=fa[y];
            if(!isroot(y)) {
                if(ch[y][1]==x^ch[z][1]==y) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
    }
    public:
        
        void init() {
            dfs(1,0),SEG_T.build(1,1,n);
            for(int i=1;i<=n;++i) left[i]=i;
            for(int j=1;j<20;j++)
                for(int i=1;i<=n;i++)
                    f[i][j]=f[f[i][j-1]][j-1];
        }
        
        void access(int x) {
            for(int t=0;x;x=fa[t=x]) {
                splay(x);
                if(rc) SEG_T.modify(1,1,n,ldfn[left[rc]],rdfn[left[rc]],1);
                rc=t;
                if(rc) SEG_T.modify(1,1,n,ldfn[left[rc]],rdfn[left[rc]],-1);
            }
            return ;
        }
        
        int query(int x) {
            int ans=0;
            for(;x;x=fa[x],ans++)splay(x);
            return ans;
        }
        
        int query(int u,int v) {
            return query(u)+query(v)-2*query(LCA(u,v))+1;
        }
#undef lc
#undef rc
}LCT;
int main() {
//	freopen("001.out","w",stdout);
    scanf("%d%d",&n,&m) ;
    for(int a,b,i=1;i<n;++i) {
        scanf("%d%d",&a,&b);
        Add_Edge(a,b);
        Add_Edge(b,a);
    }
    LCT.init();
    for(int opt,x,y,i=1;i<=m;++i) {
        scanf("%d",&opt);
        if(opt==1) scanf("%d",&x),LCT.access(x);
        if(opt==2) scanf("%d%d",&x,&y),printf("%d\n",LCT.query(x,y));
        else if(opt==3) scanf("%d",&x),printf("%d\n",SEG_T.query(1,1,n,ldfn[x],rdfn[x]));
    }
    return 0;
}